<!DOCTYPE html>
<html lang="en">

<head>
  <meta charset="UTF-8">
  <meta http-equiv="X-UA-Compatible" content="IE=edge">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <title>Document</title>
</head>

<body>
  <script>
    /**
 * @param {number[][]} grid
 * @return {number}
 * 允许向八个方向扩散, dirs中体现
 */
    var shortestPathBinaryMatrix = function (grid) {
      const n = grid.length
      if (grid[0][0] === 1 || grid[n - 1][n - 1] === 1) return -1
      let p = []
      p.push([0, 0])
      let visited = new Array(n).fill('.').map(item => new Array(n).fill(false))
      visited[0][0] = true
      const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0], [1, 1], [1, -1], [-1, 1], [-1, -1]]
      let step = 1

      while (p.length > 0) {
        let sz = p.length
        for (let _ = 0; _ < sz; _++) {
          let cur = p.shift()
          if (cur[0] === n - 1 && cur[1] === n - 1) {
            return step
          }
          // 8 为dirs的长度
          for (let i = 0; i < 8; i++) {
            let x = cur[0] + dirs[i][0]
            let y = cur[1] + dirs[i][1]
            if (x >= 0 && y >= 0 && x < n && y < n && grid[x][y] === 0 && !visited[x][y]) {
              p.push([x, y])
              visited[x][y] = true
            }
          }
        }
        step++
      }

      return -1
    };
  </script>
</body>

</html>